//给你一个二维 boolean 矩阵 grid 。 
//
// 请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目，且满足 3 个元素值 都 为 1 。 
//
// 注意： 
//
// 
// 如果 grid 中 3 个元素满足：一个元素与另一个元素在 同一行，同时与第三个元素在 同一列 ，那么这 3 个元素称为一个 直角三角形 。这 3 个元素
//互相之间不需要相邻。 
// 
//
// 
//
// 示例 1： 
//
// 
// 
// 
// 
// 0 
// 1 
// 0 
// 
// 
// 0 
// 1 
// 1 
// 
// 
// 0 
// 1 
// 0 
// 
// 
// 
// 
//
// 
// 
// 
// 0 
// 1 
// 0 
// 
// 
// 0 
// 1 
// 1 
// 
// 
// 0 
// 1 
// 0 
// 
// 
// 
//
// 
// 输入：grid = [[0,1,0],[0,1,1],[0,1,0]] 
// 
//
// 输出：2 
//
// 解释： 
//
// 有 2 个直角三角形。 
//
// 示例 2： 
//
// 
// 
// 
// 
// 1 
// 0 
// 0 
// 0 
// 
// 
// 0 
// 1 
// 0 
// 1 
// 
// 
// 1 
// 0 
// 0 
// 0 
// 
// 
// 
// 
//
// 
// 输入：grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]] 
// 
//
// 输出：0 
//
// 解释： 
//
// 没有直角三角形。 
//
// 示例 3： 
//
// 
// 
// 
// 
// 1 
// 0 
// 1 
// 
// 
// 1 
// 0 
// 0 
// 
// 
// 1 
// 0 
// 0 
// 
// 
// 
// 
//
// 
// 
// 
// 1 
// 0 
// 1 
// 
// 
// 1 
// 0 
// 0 
// 
// 
// 1 
// 0 
// 0 
// 
// 
// 
//
// 
// 输入：grid = [[1,0,1],[1,0,0],[1,0,0]] 
// 
//
// 输出：2 
//
// 解释： 
//
// 有两个直角三角形。 
//
// 
//
// 提示： 
//
// 
// 1 <= grid.length <= 1000 
// 1 <= grid[i].length <= 1000 
// 0 <= grid[i][j] <= 1 
// 
//
// Related Topics 数组 哈希表 数学 组合数学 计数 👍 33 👎 0


package LeetCode.editor.cn;


import java.util.Arrays;

/**
 * @author ldltd
 * @date 2024-08-02 19:47:53
 * @description 3128.直角三角形
 
 */
 
public class RightTriangles {
    public static void main(String[] args) {
    //测试代码
    RightTriangles fun = new RightTriangles();
    Solution solution= fun.new Solution();
    int [][]grid={{0,1,0},{0,1,1},{0,1,0}};
    int [][]grid2={{1,0,1},{1,0,0},{1,0,0}};
        System.out.println(solution.numberOfRightTriangles(grid2));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public long numberOfRightTriangles(int[][] grid) {
       int n=grid[0].length;
       int [] cSum=new int[n];
       //每一个为中心，可以形成多少的直角三角形
        //等于行个数-1 * 列个数 -1
       Arrays.fill(cSum,-1);
        for (int[] ints : grid) {
            for (int i = 0; i < n; i++) {
                cSum[i]+=ints[i];
            }
        }
        long res=0;
        for (int[] ints : grid) {
            int rSum=-1;
            for (int x : ints) {
                rSum+=x;
            }
            for (int i = 0; i < ints.length; i++) {
                if(ints[i]==1){
                    res+=rSum*cSum[i];
                }
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
